package pers.qianyu.month_202102.date_20210218;

/**
 * 995. K 连续位的最小翻转次数
 * https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/
 *
 * @author mizzle rain
 * @date 2021-02-18 20:25
 */
public class MinKBitFlips {
    // 复杂度为 O (NK) 的做法，其他语言会超时
    public int minKBitFlips(int[] A, int K) {
        int n = A.length, cnt = 0;
        int left = 0, right = K - 1;
        while (right < n) {
            if (A[left] == 0) {
                cnt++;
                for (int i = left; i <= right; i++) A[i] ^= 1;
            }
            left++;
            right++;
        }
        for (int x : A) if (x == 0) return -1;
        return cnt;
    }

    // 参考题解：https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/solution/k-lian-xu-wei-de-zui-xiao-fan-zhuan-ci-s-dseq/
    public int minKBitFlips2(int[] A, int K) {
        int n = A.length;
        int[] diff = new int[n + 1];
        int cnt = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            sum += diff[i];
            //0翻转偶数次后，数值仍然是0，需要被翻转
            //0翻转奇数次后，数值变为1，无需被翻转
            //1翻转偶数次后，数值任然是1，无需翻转
            //1翻转奇数次后，数值变为0，需要被翻转
            if (((sum & 1) ^ A[i]) == 0) {
                if (i + K > n) return -1;
                diff[i]++;
                if (i + K < n) diff[i + K]--;
                sum++;
                cnt++;
            }
        }
        return cnt;
    }
}
